#include"AVLtree.h"

template<class K, class Compare = less<K>>
class set
{
    struct set_key_of_t
    {
        const K& operator()(const K& key) const
        {
            return key;
        }
    };
    typedef AVLtree<K, const K, set_key_of_t, Compare> tree_type;
    tree_type _t;

public:
	set() {}
	set(initializer_list<K> il)
	{
		for (auto& e : il)
			_t.insert(e);
	}

    // set不可以修改容器里的数据，这里的迭代器都用AVL的const迭代器
    typedef typename tree_type::iterator         iterator;
    typedef typename tree_type::const_iterator   const_iterator;
    // 这样的话树的节点里面的_val就是const K类型
    // AVL树的普通迭代器解引用会返回const K&
    // AVL树的const迭代器解引用会返回const const K&
    
    iterator begin() { return _t.begin(); }
    iterator end() { return _t.end(); }
	const_iterator begin() const { return _t.begin(); }
    const_iterator end() const { return _t.end(); }

    // 注意set的find与AVL的find不同
    // AVL的find：找到了返回对应权值的迭代器，否则返回其父节点的迭代器
    // set的find：找到了返回对应权值的迭代器，否则返回end()
    iterator find(const K& key)
    {
        auto it = _t.find(key);
        if(it != _t.end() && *it == key)
            return it;
        else 
            return _t.end();
    }

    // 注意set的insert与AVL的insert不同
    // AVL的insert：返回值为val的迭代器
	// set的insert：返回值是pair类型，<值为val的迭代器, bool>
    pair<iterator, bool> insert(const K& val)
    {
        int old_size = _t.size();
        auto it = _t.insert(val);
        if(_t.size() == old_size) // 插入后容器大小不变，说明插入失败；否则插入成功
            return {it, false};
        else 
            return {it, true};
    }

    int erase(const K& key) { return _t.erase(key); }

    // 返回set中值为key的元素个数。找到了返回1，否则返回0
    int count(const K& key) { return find(key) != end(); }

    // 查询set中 >= key的最小的元素
    iterator lower_bound(const K& key)
    {
        if(_t.empty())  return _t.end();
        auto it = _t.find(key);  // AVL的find返回值只可能是：key / key的前驱 / key的后继 的迭代器
        if(Compare()(*it, key))   // *it < key
            ++it;
        return it;
    }

    // 查询set中 > key的最小的元素
    iterator upper_bound(const K& key)
    {
        if(_t.empty())  return _t.end();
        auto it = _t.find(key);  // AVL的find返回值只可能是：key / key的前驱 / key的后继 的迭代器
        if(Compare()(key, *it))   // *it > key
            return it;
        else
            return ++it;
    }

    int size() { return _t.size(); }
    bool empty() { return _t.empty(); }
};


template<class K, class V, class Compare = less<K>>
class map
{
	typedef pair<const K, V> T; // 键值加上const防止修改
    struct map_key_of_t
    {
        const K& operator()(const T& p) const
        {
            return p.first;
        }
    };
    typedef AVLtree<K, T, map_key_of_t, Compare> tree_type;
    tree_type _t; 
public:
	map() {}
	map(initializer_list<T> il)
	{
		for (auto& e : il)
			_t.insert(e);
	}

    typedef typename tree_type::iterator        iterator;
    typedef typename tree_type::const_iterator  const_iterator;
    iterator begin() { return _t.begin(); }
    iterator end() { return _t.end(); }
    const_iterator begin() const { return _t.begin(); }
    const_iterator end() const { return _t.end(); }

    iterator find(const K& key)
    {
		auto it = _t.find(key);
        if(it != _t.end() && it->first == key)
            return it;
        else 
            return _t.end();
    }
    
    pair<iterator, bool> insert(const T& val)
    {
        int old_size = _t.size();
        auto it = _t.insert(val);
        if(_t.size() == old_size) 
            return {it, false};
        else 
            return {it, true};
    }
    
	V& operator[](const K& key)
	{
		auto it = _t.insert({ key, V() });
		return it->second;
	}

    int count(const K& key)
    {
        auto it = _t.find(key);
        if(it == _t.end() || *it != key)
            return 0;
        else
            return 1; 
    }
};